package com.lfg.leetcode.leetcode200;

import com.lfg.leetcode.leetcode0.TreeNode;

public class No236lowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode root = TreeNode.stringToTreeNode("[3,5,1,6,2,0,8,null,null,7,4]");
        System.out.println(lowestCommonAncestor(root, TreeNode.stringToTreeNode("[5]"), TreeNode.stringToTreeNode("[1]")).val);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (null == root) {
            return null;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (null != left && null != right) {
            return root;
        }
        if (null != left) {
            return left;
        }

        if (null != right) {
            return right;
        }
        return null;
    }


}
